package class7;

import common.Node;

/**
 * 题目1：
 * 给定两个可能有环也可能无环的单链表，头肩点head1和head2,
 * 请事先一个函数，如果两个链表相交，请返回相交的第一个节点，如果不相交，返回null
 * 要求
 * 如果两个链表的长度之和为N，时间复杂度请达到 O(N)，额外空间复杂度请达到 O(1)
 * <p>
 * 环形链表:https://leetcode.cn/problems/linked-list-cycle/description/
 * 环形链表2:https://leetcode.cn/problems/c32eOV/description/
 */
public class Code02_LoopNode {
    public static void main(String[] args) {

    }

    // 返回两个链表相交的首节点
    public static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;
        // 先让两个链表走到结尾，如果有环，则两个链表尾节点不同
        while (cur1 != null) {
            cur1 = cur1.next;
            n++;
        }
        while (cur2 != null) {
            cur2 = cur2.next;
            n--;
        }
        // 当两个链表的尾节点不同时，则不相交
        if (cur1 != cur2) {
            return null;
        }
        // 判断两个链表的长短
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        n = Math.abs(n);
        // 让长链表先走n步，然后再一起走
        while (n != 0) {
            cur1 = cur1.next;
            n--;
        }
        // 当cur1 != cur2 时，说明没走到相交节点
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

}
